'''
https://leetcode.cn/problems/4sum-ii/description/
'''
from collections import defaultdict
from typing import List


class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        n = len(nums1)
        cnt1 = defaultdict(int)
        cnt2 = defaultdict(int)
        for i in range(n):
            for j in range(n):
                cnt1[nums1[i] + nums2[j]] += 1
                cnt2[nums3[i] + nums4[j]] += 1
        res = 0
        for k, v in cnt1.items():
            if -k in cnt2:
                res += v * cnt2[-k]
        return res

nums1 = [-1,-1]
nums2 = [-1,1]
nums3 = [-1,1]
nums4 = [1,-1]
print(Solution().fourSumCount(nums1, nums2, nums3, nums4))